class ListItem {
public:
    int val;
    ListItem *next;

    ListItem(int val){
        this->val = val;
        this->next = nullptr;
    }
};

class MyLinkedList {
private:
    int length;
    ListItem *head;
    ListItem *tail;

public:
    MyLinkedList() {
        this->head = new ListItem(0);
        this->tail = nullptr;
    }
    
    int get(int index) {
        ListItem *temp = this->head;
        int i = 0;

        while(i <= index) {
            if(temp->next == nullptr){
                return -1;
            }

            if(i == index){
                return temp->next->val;
            } else {
                temp = temp->next;
                i = i + 1;
            }
        }

        return -1;
    }
    
    void addAtHead(int val) {
        ListItem *item = new ListItem(val);

        if(this->tail == nullptr) {
            this->head->next = item;
            this->tail = item;
        } else {
            item->next = this->head->next;
            this->head->next = item;
        }
    }
    
    void addAtTail(int val) {
        if(this->tail == nullptr) {
            addAtHead(val);
        } else {
            ListItem *item = new ListItem(val);
            this->tail->next = item;
            this->tail = item;
        }
    }
    
    void addAtIndex(int index, int val) {
        ListItem *temp = this->head;
        int i = 0;

        while(i <= index) {
            if(temp->next == nullptr){
                if(i == index){
                    addAtTail(val);
                }
                return;
            }
            if(i == index){
                ListItem *item = new ListItem(val);
                item->next = temp->next;
                temp->next = item;
                return;
            } else {
                temp = temp->next;
                i = i + 1;
            }
        }
    }
    
    void deleteAtIndex(int index) {
        ListItem *temp = this->head;
        int i = 0;

        while(i <= index) {
            if(temp->next == nullptr){
                return;
            }

            if(i == index) {
                ListItem *item = temp->next;
                temp->next = item->next;
                
                if(item == this->tail){
                    if(temp == this->head){
                        this->tail = nullptr;
                    } else {
                        this->tail = temp;
                    }
                }

                delete(item);
                return;
            } else {
                temp = temp->next;
                i = i + 1;
            }
        }
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */